#include "HFM_Tree.h"
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#pragma warning (disable:4996)
//#define DEBUG
using namespace std;

HFM_Tree::HFM_Tree(): m_iTotalNum(0),
	m_iByteNum(0), m_idifferNum(0),
	m_pBase(NULL), m_pStatistic(NULL), 
					m_pCode(NULL){

	cout << "please input a serial of character" << endl;
	this->setStatistic(new int[128]);
	if (this->getStatistic() == NULL) {
		perror("Failed to allocate memory!\n");
		exit(EXIT_FAILURE);
	}
	text = new string;
	if (text == NULL) {
		perror("Failed to allocate memory!\n");
		exit(EXIT_FAILURE);
	}

	char ch;
	int *sttstc = getStatistic();
	memset(sttstc, 0, 128 * sizeof(int));
	while (scanf("%c", &ch) != EOF) {
		this->append(ch);
		++sttstc[(int)ch];
	}

	int count = 0;
	int sum = 0;
	for (int i = 0; i < 128; ++i) {
#ifdef DEBUG
		if ((char)i != '\n' && (char)i != '\t')
			cout << (char)i;
		else if ((char)i == '\n')
			cout << "\\n";
		else if ((char)i == '\t')
			cout << "\\t";
		cout << "  " << sttstc[i] << endl;
#endif
		if (sttstc[i] != 0) {
			sum += sttstc[i];
			++count;
		}
	}

	this->setTotalNum(sum);
	this->setdifferNum(count);

	HFM_Node *ptr = new HFM_Node[2 * count - 1];
	if (ptr == NULL) {
		perror("Failed to allocate memory!\n");
		exit(EXIT_FAILURE);
	}
	this->setBase(ptr);

	this->createTree();
	this->HFM_Code();
	this->texttoInts();
}

HFM_Tree::~HFM_Tree(){
	delete[] this->getBase();
	delete[] this->getStatistic();
	delete[] this->getInts();

	for (int i = 0; i < 128; ++i) {
		delete this->getPtrtoCode()[i];
	}
	delete[] this->getPtrtoCode();
	delete this->getText();

	this->setBase(NULL);
	this->setStatistic(NULL);
	this->setInts(NULL);
	this->setPtrtoCode(NULL);
	
}

Status HFM_Tree::HFM_Code(){
	
	string **ptr = new string*[128];
	if (ptr == NULL) {
		perror("Failed to allocate memory!\n");
		exit(EXIT_FAILURE);
	}
	this->setPtrtoCode(ptr);
	HFM_Node *ptrBase = this->getBase();
	int *sptr = this->getStatistic();
	for (int i = 0, cnt = 0; i < 128; ++i) {

		ptr[i] = new string;
		if (ptr[i] == NULL) {
			perror("Failed to allocate memory!\n");
			exit(EXIT_FAILURE);
		}
		if (sptr[i] != 0) {
			++cnt;
			for (int count = cnt - 1 ,parent = ptrBase[count].getParent(); parent != -1; ) {
				if (ptrBase[parent].getLChild() == count)
					*ptr[i] = "0" + *ptr[i];
				else if (ptrBase[parent].getRChild() == count)
					*ptr[i] = "1" + *ptr[i];
				count = parent;
				parent = ptrBase[parent].getParent();
			}
#ifdef DEBUG
			if ((char)i != '\n' && (char)i != '\t')
				cout << (char)i;
			else if((char)i == '\n')
				cout << "\\n";
			else if ((char)i == '\t')
				cout << "\\t";
			cout << "  " << *ptr[i] << endl;
#endif
		}
		
	}
	return OK;
}

Status HFM_Tree::texttoInts(){
	string *tptr = this->getText();
	string ptr;
	string **p = this->getPtrtoCode();
	for (int i = 0; i < (int)tptr->size(); ++i) {
		ptr += *p[(int)tptr->at(i)];
	}

	int size = sizeof(int) * 8;
	int psize = ptr.size();
	this->setByteNum(psize);

	int num = psize / size;
	int n = psize % size;
	if (n != 0) {
		for (int i = 0; i < size - n; ++i) {
			ptr.append("0");
		}
		++num;
	}

	int *result = new int[num];
	if (result == NULL) {
		perror("Failed to allocate memory!\n");
		exit(EXIT_FAILURE);
	}
	this->setInts(result);
	for (int i = 0; i < num; ++i) {
		result[i] = toInt(&ptr.at(i * size),size);
#ifdef DEBUG
		cout << result[i] << endl;
#endif
	}
	return OK;
}

int HFM_Tree::toInt(string ptr,int size){
	int result = 0;
	for (int i = 0; i < size; ++i) {
		result <<= 1;
		if (ptr[i] == '1') {
			result += 1;
		}
	}
	return result;
}

Status HFM_Tree::Intstotext(){
	int bytenum = this->getByteNum();
	int intsize = sizeof(int) * 8;
	int num = bytenum / intsize;
	if (bytenum % intsize != 0)
		++num;
	string str;
	int *dig = this->getInts();
	for (int i = 0; i < num; ++i) {
		str = str + tostr(dig[i]);
	}
	if (bytenum % intsize != 0) {
		num = intsize - bytenum % intsize;
		for (int i = 0; i < num; ++i) {
			str.pop_back();
		}
	}
	num = str.size();
	for (int i = 0; i < num; ) {
		cout << findChar(str,i);
	}
	return OK;
}

string HFM_Tree::tostr(int dig){
	string str;
	int size = sizeof(int) * 8;
	for (int i = 0; i < size; ++i) {
		if (dig & 1)
			str = "1" + str;
		else
			str = "0" + str;
		dig >>= 1;
	}
	return str;
}

char HFM_Tree::findChar(string &str,int &k){
	HFM_Node *root = &this->getBase()[this->getdifferNum() * 2 - 2];
	HFM_Node *ptr = root;
	do {
		if (str.at(k) == '0')
			ptr = &this->getBase()[ptr->getLChild()];
		else if(str.at(k) == '1')
			ptr = &this->getBase()[ptr->getRChild()];
		++k;
	} while (ptr->getLChild() != -1 && ptr->getRChild() != -1);

	return ptr->getChar();
}

int HFM_Tree::getdifferNum(){
	return m_idifferNum;
}

int HFM_Tree::getTotalNum(){
	return m_iTotalNum;
}

int HFM_Tree::getByteNum(){
	return m_iByteNum;
}

string **HFM_Tree::getPtrtoCode(){
	return m_pCode;
}

string * HFM_Tree::getText(){
	return text;
}

int * HFM_Tree::getInts(){
	return m_iInts;
}

HFM_Node * HFM_Tree::getBase() {
	return m_pBase;
}

int *HFM_Tree::getStatistic(){
	return m_pStatistic;
}

Status HFM_Tree::setdifferNum(int num){
	m_idifferNum = num;
	return OK;
}

Status HFM_Tree::setTotalNum(int total){
	m_iTotalNum = total;
	return OK;
}

Status HFM_Tree::setByteNum(int byteNum){
	m_iByteNum = byteNum;
	return OK;
}

Status HFM_Tree::setPtrtoCode(string **ptr){
	m_pCode = ptr;
	return OK;
}

Status HFM_Tree::append(char ch){
	*text = *text + ch;
	return OK;
}

Status HFM_Tree::setInts(int *ptr){
	this->m_iInts = ptr;
	return OK;
}

Status HFM_Tree::setBase(HFM_Node *base){
	m_pBase = base;
	return OK;
}

Status HFM_Tree::setStatistic(int *base){
	m_pStatistic = base;
	return OK;
}

Status HFM_Tree::createTree(){
	double sum = this->getTotalNum();
	HFM_Node *ptr = this->getBase();
	int *iptr = this->getStatistic();
	int n = this->getdifferNum();

	int count = 0;
	for (int i = 0; i < 128; ++i) 
		if (iptr[i] != 0) {
			ptr[count].setChar((char)i);
			ptr[count].setWeight(iptr[i] / sum);
			++count;
		}
	int parent = count;
	for (; parent < 2 * n - 1; ++parent) {
		double w1 = 0;
		double w2 = 0;

		int lChild = -1;
		int rChild = -1;
		for (int i = 0; i < parent; ++i) {
			if (ptr[i].getParent() == -1) {
				if (w1 == 0) {
					w1 = ptr[i].getWeight();
					lChild = i;
					continue;
				}
				if (w2 == 0) {
					w2 = ptr[i].getWeight();
					rChild = i;
					if (w1 > w2) {
						rChild = lChild;
						lChild = i;
						double temp = w1;
						w1 = w2;
						w2 = temp;
					}
					continue;
				}
				if (w1 > ptr[i].getWeight()) {
					rChild = lChild;
					lChild = i;
					w2 = w1;
					w1 = ptr[i].getWeight();
				}
				else if (w2 > ptr[i].getWeight()) {
					w2 = ptr[i].getWeight();
					rChild = i;
				}
			}
		}

		ptr[lChild].setParent(parent);
		ptr[rChild].setParent(parent);
		ptr[parent].setLChild(lChild);
		ptr[parent].setRChild(rChild);
		ptr[parent].setWeight(w1 + w2);
	}
	return OK;
}

